package ljl.codetop300;

/**
 * 我擦！规划啥你规划，别人俩变量解决了你在这规划，还
 */
public class _offer_42_contiguous_max_subarray_sum {

  public static void main(String[] args) {
    System.out.println(new _offer_42_contiguous_max_subarray_sum().maxSubArray(new int[]{-1}));
  }
  /**
   * 有一种感觉，用动态规划
   */
  public int maxSubArray(int[] nums) {
    int len = nums.length;
    int[] dp = new int[len + 1];
    for (int i = 1; i <= len; i++) {
      int value = dp[i - 1] + nums[i - 1];
      dp[i] = Math.max(value, nums[i - 1]);
    }
    int max = Integer.MIN_VALUE;
    for (int i = 1; i <= len; i++) {
      if (dp[i] > max) max = dp[i];
    }
    return max;
  }

  static class lu_fei {
    public int maxSubArray(int[] nums) {
      int res = nums[0];
      for(int i = 1; i < nums.length; i++) {
        nums[i] += Math.max(nums[i - 1], 0);
        res = Math.max(res, nums[i]);
      }
      return res;
    }

  }

  /**
   * 我透？
   */
  static class changed {
    public int maxSubArray(int[] nums) {
      int res = nums[0], max = res;
      for(int i = 1; i < nums.length; i++) {
        res = Math.max(res + nums[i], nums[i]);
        max = Math.max(max, res);
      }
      return max;
    }
  }
}
